package kcsj;

import sxx.MyUtil;

import java.io.InputStream;
import java.util.Arrays;
import java.util.Scanner;

public class OptimalManyServices {
    int n0;//人
    int[] t0;//服务时间
    int s0;//服务点

    public OptimalManyServices(int index) {
        InputStream fin = MyUtil.class.getResourceAsStream("/data/OptimalManyServices/test/waits" + index + ".in");
        assert fin != null : "找不到测试数据!";
        Scanner scanner = new Scanner(fin);
        n0 = scanner.nextInt();
        s0 = scanner.nextInt();
        t0 = new int[n0];
        for (int i = 0; scanner.hasNext(); i++) {
            t0[i] = scanner.nextInt();
        }
    }

    public float solve() {
        float time = 0;
        int[] n = new int[s0];
        int[][] t = new int[s0][(n0 / s0) + 1];

        //排序
        Arrays.sort(t0);
        //分组
        for (int i = 0; i < s0; i++) {
            for (int j = i; j < t0.length; j += s0) {
                t[i][n[i]++] = t0[j];
            }
        }
        //计算使时间
        for (int i = 0; i < s0; i++) {
            for (int j = 0; j < n[i]; j++) {
                time += (n[i] - j) * t[i][j];
            }
        }
        return time / n0;
    }

    public float solve1() {
        //排序
        Arrays.sort(t0);
        float sum = 0;
        int[] a = new int[s0];//顾客在服务所等待的时间
        int[] b = new int[s0];//在服务点服务的所有顾客的总等待时间
        Arrays.fill(a, 0);//初始化(不用也可以)
        Arrays.fill(b, 0);//同上
        for (int i = 0, s = 0; i < t0.length; i++) {
            a[s] += t0[i];//a[k]:顾客i在s处服务所等待的时间
            b[s] += a[s];//b[k]:顾客在j处服务点服务的总等待时间
            s += 1;//下一个服务点上客
            if (s == s0) s = 0;//所有服务点轮完,重新从第一个服务点开始轮
        }
        for (int i = 0; i < s0; i++) {
            sum += b[i];//所有服务点的总等待时间相加
        }
        //返回均值
        return sum / n0;
    }

    public static void main(String[] args) {
        for (int i = 0; i <= 10; i++) {
            float a = new OptimalManyServices(i).solve();
            System.out.println(i + ". " + a);
        }
    }
}
